//
//  BinarySearchTreeView.swift
//  DataStructure
//
//  Created by kys-20 on 2019/9/3.
//  Copyright © 2019 kys-20. All rights reserved.
//
//  二叉搜索树 没写完没写完没写完===================记得赶紧写=================



import Foundation
import UIKit

class BinarySearchTreeView: UIScrollView {

    var tree : BinarySearchTree<Int, Int>?
    var myType : Int!
    var printLabelNum = [UILabel]()
    var arrWH: [Int]!

  var textFiled = UITextField()
    var deleteLabelArray = [UILabel]()
  var insterButton = UIButton()//插入按钮
  var deleteButton = UIButton()//删除按钮
    var findButton = UIButton()//搜索按钮
    var printButton = UIButton()//输出按钮
  var intArray = [Int]()// 按插入顺序存入数组
  var labArray = [UILabel]()//插入顺序存放label
  var rootArray = [Int]()//树的先序数组根左右
    var circularLabel = UILabel()
   var startingPosition : CGPoint = CGPoint(x: UIScreen.main.bounds.width/2, y: 120)//第一个label的起始位置
    let labelWAndH : CGFloat = 60
  var sumTimer = 1.00//每一步动画总时间
  private var timer:Timer!//检测
  private var timerMove:Timer!//移动
  private var timerMoveOther:Timer!//移动其他label
  //贝塞尔曲线
  var pathArray = [UIBezierPath]()
  var shapeLayerArray = [CAShapeLayer]()
    
    var precursorInt : Int!
    var leftOrRight : Int!
    var precursorPoint:CGPoint!
    var point :CGPoint!
    var timerNum = 0.00000
    
    
    override init(frame: CGRect) {
        super.init(frame: frame)
        self.contentSize = CGSize(width: UIScreen.main.bounds.width*2, height: UIScreen.main.bounds.height*1.5)
        setUpUI()
    }
    required init?(coder aDecoder: NSCoder) {
        fatalError("init(coder:) has not been implemented")
    }

}
//MARK: - 插入节点动画操作
extension BinarySearchTreeView{
    //判断 是否可以进行插入操作
     @objc func isInsterAction(){
        circularLabel.isHidden = true
             if textFiled.text != "" {
                 let int = Int(textFiled.text!)
                 if !intArray.contains(int!){
                     intArray.append(int!)
                    playInsterAction(int: int!)
                 }
             }
      }
    //根据不同情况创建了新的label
    func playInsterAction(int: Int){
        if labArray.count == 0{
                 setUpLabel(cen: startingPosition, text: int)
                 let node = Node<Int, Int>(key: int, value: int)
                 tree = BinarySearchTree(node)
             }else{
                 setLine()//添加直线

                 setUpLabel(cen: CGPoint(x: 30, y: 120), text: int)
                 tree!.put(key: int, value: int)
                self.rootArray.removeAll()
                tree!.preOrder()
                self.rootArray = tree!.getNodeArray()

                 precursorInt = getPrecursor(arr:rootArray, targetLabelTag: labArray.last!.tag)
                 leftOrRight = getLeftAndRight(int:labArray.last!.tag)
                 precursorPoint = getOneLabel(tag:precursorInt)
                 point = calculationNextLabel(startPoint:precursorPoint,leftOrRight:leftOrRight)
            
            
            if leftOrRight == 0{
                if isHaveLabel(center: point){
                    self.timerMoveOther = Timer.scheduledTimer(timeInterval: 0.001, target: self, selector: #selector(moveOtherLabelTimerActionTwo), userInfo: nil, repeats: true)
                   timerMove = Timer.scheduledTimer(timeInterval: 0.001, target: self, selector: #selector(timeMoveLabelAvtionTwo), userInfo: nil, repeats: true)
                }else{
                     timerMove = Timer.scheduledTimer(timeInterval: 0.001, target: self, selector: #selector(timeMoveLabelAvtion), userInfo: nil, repeats: true)
                }
            }else{
                if isHaveLabel(center: point){
                    self.timerMoveOther = Timer.scheduledTimer(timeInterval: 0.001, target: self, selector: #selector(moveOtherLabelTimerAction), userInfo: nil, repeats: true)
                   timerMove = Timer.scheduledTimer(timeInterval: 0.001, target: self, selector: #selector(timeMoveLabelAvtion), userInfo: nil, repeats: true)
                }else{
                     timerMove = Timer.scheduledTimer(timeInterval: 0.001, target: self, selector: #selector(timeMoveLabelAvtion), userInfo: nil, repeats: true)
                }
            }
       }
        
    }
    
    @objc func moveOtherLabelTimerAction(){

        
         moveOtherLabel(center:point, type: leftOrRight)
    }
    
    @objc func moveOtherLabelTimerActionTwo(){
        let poin = CGPoint(x: point.x + 60.00, y: point.y)
        moveOtherLabel(center:poin, type: leftOrRight)
    }
    
    //移动新的label
    @objc func timeMoveLabelAvtion(){
 
        moveUnit(label:labArray.last!,point:point,type:leftOrRight)
        moveLine()
        if fabsf(Float(labArray.last!.center.x - point.x)) < 0.5 {
            timerMove.invalidate()
            if timerMoveOther != nil{
                timerMoveOther.invalidate()
            }
        }
    }
    
    
    //移动新的label
    @objc func timeMoveLabelAvtionTwo(){
        let poin = CGPoint(x: point.x + 60.00, y: point.y)
        moveUnit(label:labArray.last!,point:poin,type:leftOrRight)
        moveLine()
        if fabsf(Float(labArray.last!.center.x - poin.x)) < 0.5 {
            timerMove.invalidate()
            if timerMoveOther != nil{
                timerMoveOther.invalidate()
            }
        }
    }
    
    //移动直线
       func moveLine(){
           for i in 0...rootArray.count-1{
               if i%3 == 1{
                   if rootArray[i] != -9999{
                       let sub = getSubscript(element: rootArray[i])
                       pathArray[sub].removeAllPoints()
                       pathArray[sub].move(to: getTagCenter(tag: rootArray[i-1]))
                       pathArray[sub].addLine(to: getTagCenter(tag: rootArray[i]))
                       shapeLayerArray[sub].path = pathArray[sub].cgPath
                   }
               }
               if i%3 == 2{
                   if rootArray[i] != -9999{
                       let sub = getSubscript(element: rootArray[i])
                       pathArray[sub].removeAllPoints()
                       pathArray[sub].move(to: getTagCenter(tag: rootArray[i-2]))
                       pathArray[sub].addLine(to: getTagCenter(tag: rootArray[i]))
                       shapeLayerArray[sub].path = pathArray[sub].cgPath
                   }
               }
           }
       }
    
    //返回 数组下标-1
    func getSubscript(element:Int) -> Int{
        var sub : Int!
        for i in 0..<intArray.count{
            if intArray[i] == element{
                sub = i-1
            }
        }
        return sub
    }
    
    //找到tag一直的label的center
    func getTagCenter(tag:Int) -> CGPoint{
        var tagPoint : CGPoint!
        for i in labArray{
            if i.tag == tag{
                tagPoint = i.center
            }
        }
        return tagPoint
    }
 
}
//MARK: - 删除Label的操作

extension BinarySearchTreeView{
    @objc func isdeleteAction(){
        circularLabel.isHidden = true
        if textFiled.text != "" {
            let int = Int(textFiled.text!)
             if intArray.contains(int!){
                    
                        if labArray.count == 1{
                            labArray[0].removeFromSuperview()
                            labArray.removeAll()
                            intArray.removeAll()
                        }else{
                            deleteAction(int:int!)
                        }
                 }
           }
    }
    
    func deleteAction(int:Int){
        if isHaveRoot(int:int) == 0{
            deleteNumOne(int:int)
        }else if isHaveRoot(int:int) == 11{
            deleteNumOneOne(int:int)
        }else if isHaveRoot(int:int) == 12{
            deleteNumOneOne(int:int)
        }else if isHaveRoot(int:int) == 2{
            
        }
    }
    
    func deleteNumOne(int:Int){
         tree?.delete(key: int)
         self.rootArray.removeAll()
         tree!.preOrder()
         self.rootArray = tree!.getNodeArray()
        if intArray.count > 1{
           pathArray[getSubscript(element: int)].removeAllPoints()
            shapeLayerArray[getSubscript(element: int)].path = pathArray[getSubscript(element: int)].cgPath
           pathArray.remove(at: getSubscript(element: int))
           shapeLayerArray.remove(at: getSubscript(element: int))
        }
        labArray[getSubscript(element: int)+1].removeFromSuperview()
        labArray.remove(at: getSubscript(element: int)+1)
        intArray.remove(at: getSubscript(element: int)+1)
    }
    
    func deleteNumOneOne(int:Int){
        
        deleteLabelArray.removeAll()
        findOtherLabelDelete(int:int)
        if isHaveRoot(int:int) == 11{
          timer = Timer.scheduledTimer(timeInterval: sumTimer/1000, target: self, selector: #selector(moveDeletaLabel), userInfo: nil, repeats: true)
        }else if isHaveRoot(int:int) == 12{
            
            timer = Timer.scheduledTimer(timeInterval: sumTimer/1000, target: self, selector: #selector(moveDeletaLabelA), userInfo: nil, repeats: true)
        }
        
        
        
         tree?.delete(key: int)
         self.rootArray.removeAll()
         tree!.preOrder()
         self.rootArray = tree!.getNodeArray()
        if intArray.count > 1{
           pathArray[getSubscript(element: int)].removeAllPoints()
            shapeLayerArray[getSubscript(element: int)].path = pathArray[getSubscript(element: int)].cgPath
           pathArray.remove(at: getSubscript(element: int))
           shapeLayerArray.remove(at: getSubscript(element: int))
        }
        labArray[getSubscript(element: int)+1].removeFromSuperview()
        labArray.remove(at: getSubscript(element: int)+1)
        intArray.remove(at: getSubscript(element: int)+1)
        
    }
    
    @objc func moveDeletaLabel(){
        for i in deleteLabelArray{
            let x = i.center.x + labelWAndH/CGFloat(1000*sumTimer)
            let y = i.center.y - labelWAndH/CGFloat(1000*sumTimer)
            i.center = CGPoint(x: x, y: y)
        }
        timerNum = timerNum + 1
        moveLine()
        if timerNum >= 1000*sumTimer{
            timerNum = 0
            timer.invalidate()
        }
    }
    @objc func moveDeletaLabelA(){
        for i in deleteLabelArray{
            let x = i.center.x
            let y = i.center.y - labelWAndH/CGFloat(1000*sumTimer)
            i.center = CGPoint(x: x, y: y)
        }
        timerNum = timerNum + 1
        moveLine()
        if timerNum >= 1000*sumTimer{
            timerNum = 0
            timer.invalidate()
        }
    }
    
    func findOtherLabelDelete(int:Int){
         for i in 0...rootArray.count-1{
            if i%3 == 0 && rootArray[i] == int{
                if rootArray[i+1] != -9999{
                    findOtherLabelDelete(int:rootArray[i+1])
                    deleteLabelArray.append(getOneUIlabel(int:rootArray[i+1]))
                }
                if rootArray[i+2] != -9999{
                    findOtherLabelDelete(int:rootArray[i+2])
                     deleteLabelArray.append(getOneUIlabel(int:rootArray[i+2]))
                }
            }
        }
    }
    
    /// 得到某一个label
    /// - Parameter int: <#int description#>
    func getOneUIlabel(int:Int) -> UILabel{
        var label : UILabel!
        for i in labArray{
            if i.tag == int{
                label = i
            }
        }
        return label
    }
    
    /// 判断该节点是否有跟
    /// - Parameter int: 目标label的tag
    func isHaveRoot(int:Int) -> Int{
        var rootNum = 0
        for i in 0...rootArray.count-1{
            if i%3 == 0 && rootArray[i] == int{
                if rootArray[i+1] != -9999{
                    rootNum = 11
                }
                if rootArray[i+2] != -9999{
                    rootNum = 12
                }
                if rootArray[i+1] != -9999 && rootArray[i+2] != -9999{
                    rootNum = 2
                }
            }
        }
        
        
        return rootNum
    }
}





//MARK: - 各种label的移动方法
extension BinarySearchTreeView{
    //有两种移动label的方式 - 1只移动一个label 2移动目标label右边所有的label
    
    //每一次移动单位距离0为移动到左边 1为移动到右边
    
    /// 移动一个label
    /// - Parameter label: 目标label
    /// - Parameter point: 移动到的位置
    /// - Parameter type: 移动的方向 0 左 1 右
      func moveUnit(label:UILabel,point:CGPoint,type:Int){
          
          if type == 0 {
              let x = label.center.x + (point.x - 30.00)/CGFloat(1000*sumTimer)
              let y = label.center.y + (point.y - 120.00)/CGFloat(1000*sumTimer)
              label.center = CGPoint(x: x, y: y)
          }else if type == 1{
              let x = label.center.x + ((point.x - 30.00)/CGFloat(1000*sumTimer))
              let y = label.center.y + (point.y - 120.00)/CGFloat(1000*sumTimer)
              label.center = CGPoint(x: x, y: y)
          }
//          moveLine()
      }
    

     
    
    
    // 移动其他圆形label 根据Center 判断 那些 label该移动
    func moveOtherLabel(center:CGPoint,type:Int){
        
        if type == 1{
            for i in labArray{
                if fabsf(Float(i.center.x - center.x)) < 10 || i.center.x > center.x{
                    let x = i.center.x + (60.00)/CGFloat(1000*sumTimer)
                    let y = i.center.y
                    i.center = CGPoint(x: x, y: y)
                }
            }
        }else if type == 0{
            for i in labArray{//fabsf(Float((i.center.x - 60.00) - center.x)) < 10
                if fabsf(Float(i.center.x - center.x)) < 10 || i.center.x > center.x{
                    let x = i.center.x + (60.00)/CGFloat(1000*sumTimer)
                    let y = i.center.y
                    i.center = CGPoint(x: x, y: y)
                }
            }
        }
    }
    

    //判断 该点 垂直范围内 是否有label
       func isHaveLabel(center:CGPoint) -> Bool{
           var isHave = false
               for i in labArray{
                   if fabsf(Float(i.center.x - center.x)) < 20{
                       isHave = true
                   }
               }
           return isHave
       }
    
}

//MARK: -  label应该移动到什么位置
extension BinarySearchTreeView{
    
    /// 得到某一个label的位置
    /// - Parameter tag:
    func getOneLabel(tag:Int) -> CGPoint{
        var point: CGPoint!
        for i in labArray{
            if i.tag == tag{
                point = i.center
            }
        }
        return point
    }
    /// 计算label应该去的位置
    /// - Parameter startPoint: 根节点
    /// - Parameter leftOrRight: 左节点还是右节点 0代表左，1代表右
    func calculationNextLabel(startPoint:CGPoint,leftOrRight:Int) -> CGPoint{
        var endPoint: CGPoint = CGPoint(x: 0, y: 0)
        if leftOrRight == 0{
            endPoint.x = startPoint.x - labelWAndH
            endPoint.y = startPoint.y + labelWAndH
        }else if leftOrRight == 1{
            endPoint.x = startPoint.x + labelWAndH
            endPoint.y = startPoint.y + labelWAndH
        }
        return endPoint
    }
    
    /// 找到目标label的父节点
    /// - Parameter arr: 树数组
    /// - Parameter targetLabelTag: 目标label的tag
    func getPrecursor(arr:[Int],targetLabelTag:Int) -> Int{
        var pTag : Int!
        for i in 0...arr.count-1{
            if arr[i] == targetLabelTag {
                if i%3 == 1{
                    pTag = arr[i-1]
                }else if i%3 == 2{
                    pTag = arr[i-2]
                }
            }
        }
        return pTag
    }
    
    func getLeftAndRight(int:Int) -> Int{
        if int < getPrecursor(arr:rootArray, targetLabelTag: labArray.last!.tag) {
            return 0
        }else{
            return 1
        }
    }
}




//MARK: - 创建视图方法
extension BinarySearchTreeView{
         func setUpUI(){
            
            circularLabel.frame = CGRect(x: 0, y: 0, width: labelWAndH, height: labelWAndH)
            circularLabel.layer.borderWidth = 4
            circularLabel.layer.borderColor = UIColor.red.cgColor
            circularLabel.layer.cornerRadius = labelWAndH/2
            self.addSubview(circularLabel)
            circularLabel.isHidden = true
            
                textFiled.frame = CGRect(x: 20, y: 40, width: 70, height: 40)
                textFiled.layer.borderColor = UIColor.red.cgColor
                textFiled.layer.borderWidth = 1
                self.addSubview(textFiled)
                insterButton.frame = CGRect(x: 100, y: 40, width: 70, height: 40)
                insterButton.backgroundColor = UIColor.white
                insterButton.setTitle("Insert", for:.normal)
            insterButton.layer.borderWidth = 1
            insterButton.layer.borderColor = UIColor.black.cgColor
                insterButton.setTitleColor(UIColor.black, for: .normal)
                insterButton.setTitleColor(UIColor.brown, for: .highlighted)
                insterButton.addTarget(self, action: #selector(isInsterAction), for: .touchUpInside)
                self.addSubview(insterButton)
                
                deleteButton.frame = CGRect(x: 180, y: 40, width: 70, height: 40)
                deleteButton.backgroundColor = UIColor.white
                deleteButton.setTitle("Delete", for:.normal)
            deleteButton.layer.borderWidth = 1
            deleteButton.layer.borderColor = UIColor.black.cgColor
                deleteButton.setTitleColor(UIColor.black, for: .normal)
                deleteButton.setTitleColor(UIColor.brown, for: .highlighted)
                deleteButton.addTarget(self, action: #selector(isdeleteAction), for: .touchUpInside)
                self.addSubview(deleteButton)
            findButton.frame = CGRect(x: 260, y: 40, width: 70, height: 40)
            findButton.backgroundColor = UIColor.white
            findButton.setTitle("Find", for:.normal)
             findButton.layer.borderWidth = 1
             findButton.layer.borderColor = UIColor.black.cgColor
            findButton.setTitleColor(UIColor.black, for: .normal)
            findButton.setTitleColor(UIColor.brown, for: .highlighted)
            findButton.addTarget(self, action: #selector(findAction), for: .touchUpInside)
            self.addSubview(findButton)
            
            printButton.frame = CGRect(x: 340, y: 40, width: 70, height: 40)
            printButton.backgroundColor = UIColor.white
            printButton.setTitle("Print", for:.normal)
             printButton.layer.borderWidth = 1
             printButton.layer.borderColor = UIColor.black.cgColor
            printButton.setTitleColor(UIColor.black, for: .normal)
            printButton.setTitleColor(UIColor.brown, for: .highlighted)
            printButton.addTarget(self, action: #selector(printAction), for: .touchUpInside)
            self.addSubview(printButton)
            
            }
    
        //建立直线
        func setLine(){
            let path = UIBezierPath()
            let shapeLayer = CAShapeLayer()
            path.move(to: CGPoint(x: 0, y: 0))
            path.addLine(to: CGPoint(x: 0, y: 0))
            path.close()
            
            shapeLayer.strokeColor = UIColor.red.cgColor
            shapeLayer.fillColor = UIColor.clear.cgColor
            shapeLayer.lineWidth = 1
            shapeLayer.lineJoin = CAShapeLayerLineJoin.round
            shapeLayer.lineCap = CAShapeLayerLineCap.round
            shapeLayer.path = path.cgPath
            shapeLayer.strokeStart = 0
            shapeLayer.strokeEnd = 1
            self.layer.addSublayer(shapeLayer)
            shapeLayerArray.append(shapeLayer)
            pathArray.append(path)
        }
        //创建圆形label
          func setUpLabel(cen:CGPoint,text:Int){
              let label = UILabel()
              label.frame.size = CGSize(width: labelWAndH, height: labelWAndH)
              label.center = cen
              label.text = String(text)
              label.tag = text
              label.layer.cornerRadius = 30
              label.layer.borderColor = UIColor.green.cgColor
              label.layer.borderWidth = 1
              label.textAlignment = .center
              labArray.append(label)
              self.addSubview(label)
          }
}
//MARK: - Print
extension BinarySearchTreeView{
    @objc func printAction(){
        circularLabel.isHidden = true
        arrWH = intArray
        arrWH.sort(){$0 < $1}
        printLabelNu(num: 0)
        
    }
    
    func printLabelNu(num: Int){
        let label = UILabel()
        label.textColor = UIColor.black
        label.text = String(arrWH[num])
        label.backgroundColor = UIColor.clear
        label.frame.size = CGSize(width: labelWAndH, height: labelWAndH)
        label.center = getOneLabel(tag:arrWH[num])
        self.addSubview(label)
        
        UIView.animate(withDuration: 0.5, animations: {
            label.center = CGPoint(x: CGFloat(num+1)*self.labelWAndH, y: 400)
        }) { (_) in
            if num < self.arrWH.count-1{
                self.printLabelNu(num: num+1)
            }
        }
          
    }
    
}
//MARK: - Find
extension BinarySearchTreeView{
   @objc func findAction(){
    circularLabel.isHidden = true
        if textFiled.text != "" {
           let int = Int(textFiled.text!)
            self.rootArray.removeAll()
            tree!.preOrder()
            self.rootArray = tree!.getNodeArray()
            circularLabel.isHidden = false
            getFind(text:int!, star: intArray[0])
            
       }
    }
    
    func getBigChild(num: Int) -> Int{
        var bigChild : Int!
        for i in 0..<rootArray.count{
            if i%3 == 0 && rootArray[i] == num{
                bigChild = rootArray[i+2]
            }
        }
        return bigChild
    }
    
    func getSmallChild(num: Int) -> Int{
           var smallChild : Int!
           for i in 0..<rootArray.count{
               if i%3 == 0 && rootArray[i] == num {
                print(rootArray[i+1])
                   smallChild = rootArray[i+1]
               }
           }
           return smallChild
    }
    
    
    func getFind(text:Int,star:Int){
        
        UIView.animate(withDuration: 0.8, animations: {
            self.circularLabel.center = self.getOneLabel(tag: star)
        }) { (_) in

            if text > star{
                self.getFind(text:text,star:self.getBigChild(num: star))
            }else if text < star {
                self.getFind(text:text,star:self.getSmallChild(num: star))
            }
            
            
        }
    }
    
}
